/**
 * 
 */
package com.module.hq.graph;

import java.util.ArrayList;
import java.util.Stack;

import com.dalonedrau.graph.GraphEdge;
import com.dalonedrau.graph.SparseGraph;

/**
 * @author Donald
 */
public class HQGraphSearchDepthFirst {
	private static final int	NO_PARENT_ASSIGNED	= -3;
	private static final int	UNVISITED			= -2;
	private static final int	VISITED				= -1;
	/** flag indicating that the target has been found. */
	private boolean				found;
	/** the graph being searched. */
	private HQCellGraph			graph;
	/** the route to the target. */
	private int[]				route;
	/** the source node from where the search originates. */
	private int					source;
	/** the target node from where the search ends. */
	private int					target;
	/** the vector of all nodes visited as part of the search. */
	private int[]				visited;
	/**
	 * Creates a new instance of {@link HQGraphSearchDepthFirst}.
	 * @param graph
	 */
	public HQGraphSearchDepthFirst(final HQCellGraph g) {
		graph = g;
		source = -1;
		target = -1;
		found = false;
		visited = new int[graph.getNumberOfNodes()];
		for (int i = 0; i < visited.length; i++) {
			visited[i] = HQGraphSearchDepthFirst.UNVISITED;
		}
		route = new int[graph.getNumberOfNodes()];
		for (int i = 0; i < route.length; i++) {
			route[i] = HQGraphSearchDepthFirst.NO_PARENT_ASSIGNED;
		}
	}
	public void clear() {
		source = -1;
		target = -1;
		found = false;
		for (int i = 0; i < visited.length; i++) {
			visited[i] = HQGraphSearchDepthFirst.UNVISITED;
		}
		for (int i = 0; i < route.length; i++) {
			route[i] = HQGraphSearchDepthFirst.NO_PARENT_ASSIGNED;
		}
	}
	/**
	 * Gets the graph
	 * @return {@link SparseGraph}
	 */
	public HQCellGraph getGraph() {
		return graph;
	}
	public Integer[] getPathToTarget() {
		ArrayList<Integer> path = new ArrayList<Integer>();
		// just return an empty path if no path to target found or if
		// no target has been specified
		// if there is no path to the target, or no target was specified,
		// an empty path is returned. otherwise, the path is filled below
		if (found && target >= HQCellGraph.INVALID_NODE_INDEX) {
			int node = target;
			path.add(node);
			while (node != source) {
				node = route[node];
				path.add(0, node);
			}
		}
		return path.toArray(new Integer[path.size()]);
	}
	/**
	 * Determines if the target node has been found.
	 * @return true if the target node has been found; false otherwise
	 */
	public boolean isFound() {
		return found;
	}
	public void search(final int src, final int targ) throws Exception {
		source = src;
		target = targ;
		for (int i = 0; i < visited.length; i++) {
			visited[i] = HQGraphSearchDepthFirst.UNVISITED;
		}
		for (int i = 0; i < route.length; i++) {
			route[i] = HQGraphSearchDepthFirst.NO_PARENT_ASSIGNED;
		}
		found = searchDepthFirst();
	}
	private boolean searchDepthFirst() throws Exception {
		// create a stack of edges
		Stack<GraphEdge> stack = new Stack<GraphEdge>();
		// create an initial dummy edge and push it on the stack
		GraphEdge dummy = new GraphEdge(source, source);
		stack.push(dummy);
		// while there are edges on the stack keep searching
		while (!stack.isEmpty()) {
			// grab the next edge
			GraphEdge next = stack.pop();
			// make a note of the parent of the node this edge points to
			route[next.getTo()] = next.getFrom();
			// mark the edge's destination node as visited
			visited[next.getTo()] = HQGraphSearchDepthFirst.VISITED;

			// test for termination. If the edge's destination node is
			// the target node, then the search can return success
			if (next.getTo() == target) {
				return true;
			}
			// push all edges from the node the current edge points to
			// onto the stack. ignore all edges that point to a node that
			// has been visited
			GraphEdge[] edges = graph.getEdgesFromNode(next.getTo());
			for (int i = 0; i < edges.length; i++) {
				if (visited[edges[i].getTo()] == HQGraphSearchDepthFirst.UNVISITED) {
					stack.push(edges[i]);
				}
			}
		}
		return false;
	}
}
